package com.qying.limit;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 滑动窗口算法
 * 解决固定窗口临界值的问题,将单位时间周期分为n个小周期，分别记录每个小周期内
 * 接口的访问次数,并且根据时间滑动删除过期的小周期
 *
 * 例：单位时间为 1s,滑动窗口算法会划分为5个小周期类似 1-1.2， 1.2-1.4
 *    每个小周期为0.2s,每隔0.2窗口像右滑动一格,每个小周期有自己独立的计数器
 *    如果请求是0.83s到达的,0.8-1.0对应的计数器加1
 * 如何解决临界问题的：
 *    如果1s内 限流阈值为5,
 *    0.8 - 1.0 内来了5个请求,时间过了 1.0s 又来了5个请求,如果是固定串口算法
 *    是不会限流的,但是滑动窗口,每过一个小周期,会往右移动一个小格。过了1.0以后
 *    当前单位时间段为 0.2 - 1.2s ,这个区域请求超过限定的5,触发限流了
 *  TIPS:
 *     当滑动窗口的格子周期划分越多,滑动窗口就越平滑,限流统计就会越精确
 *
 *
 * 滑动窗口算法虽然解决了固定窗口的临界问题，但是一旦到达限流后，请求都会直接暴力
 * 被拒绝。酱紫我们会损失一部分请求，这其实对于产品来说，并不太友好。
 *
 *
 */
public class SlideLimit {

    //循环队列,装多个窗口用,改数量是windowSize的2倍
    private AtomicInteger[] timeSlices;

    //队列的总长度
    private int timeSliceSize;

    //每个时间片的时长,以毫秒为单位
    private int timeMillisPerSlice;

    //共有多少个时间片(即窗口长度)
    private int windowsSize;

    //在一个完整的窗口期允许通过的最大阈值
    private int threshold;

    //滑动窗口的起始创建时间,第一个数据
    private long beginTimeStamp;

    //最后一个数据的时间戳
    private long lastAddTimeStamp;

    public static void main(String[] args) throws InterruptedException {
        SlideLimit slideLimit = new SlideLimit(100,4,8);
        for (int i = 0; i < 100; i++) {
            System.out.println(slideLimit.addCount(2));

            slideLimit.print();

            System.out.println("-----------------");

            Thread.sleep(102);
        }
    }

    public SlideLimit(int duration, int threshold) {

        if (duration > 600) {
            duration = 600;
        }

        if (duration <=5) {
            this.windowsSize = 5;
            this.timeMillisPerSlice = duration * 200;
        } else {
            this.windowsSize = 10;
            this.timeMillisPerSlice = duration * 100;
        }

        this.threshold = threshold;
        this.timeSliceSize = windowsSize * 2;
        reset();
    }

    public SlideLimit(int timeMillisPerSlice, int windowsSize, int threshold) {
        this.timeMillisPerSlice = timeMillisPerSlice;
        this.windowsSize = windowsSize;
        this.threshold = threshold;

        this.timeSliceSize = windowsSize * 2;
        reset();
    }

    private void reset() {
        beginTimeStamp = SystemClock.now();
        AtomicInteger[] localTimeSlices = new AtomicInteger[timeSliceSize];

        for (int i = 0; i < timeSliceSize; i++) {
            localTimeSlices[i] = new AtomicInteger(0);
        }
        timeSlices = localTimeSlices;
    }

    private void print() {
        for (AtomicInteger timeSlice : timeSlices) {
            System.out.println(timeSlice + "-");
        }
    }

    private int locationIndex() {
        long now = SystemClock.now();

        if (now - lastAddTimeStamp > timeMillisPerSlice * windowsSize) {
            reset();
        }

        return (int) (((now - beginTimeStamp)/ timeMillisPerSlice)% timeSliceSize);
    }

    public boolean addCount(int count) {
        int index = locationIndex();
        clearFromIndex(index);
        int sum = 0;

        sum += timeSlices[index].addAndGet(count);

        for (int i = 0; i < windowsSize; i++) {
            sum += timeSlices[(index - i + timeSliceSize) % timeSliceSize].get();
        }

        System.out.println(sum + "---" + threshold);

        lastAddTimeStamp = SystemClock.now();

        return sum >= threshold;
    }

    private void clearFromIndex(int index) {
        for (int i = 0; i < windowsSize; i++) {
            int j = index + i;
            if (j >= windowsSize * 2) {
                j-=windowsSize * 2;
            }
            timeSlices[j].set(0);
        }
    }
    /*// 单位时间划分的小周期
    private int SUB_CYCLE = 10;

    //每分钟限流请求数
    private int thresholdPerMin=100;

    //计数器,k-为当前窗口的开始时间值 秒, value为当前窗口的计数
    private final TreeMap<Long, Integer> counters = new TreeMap<>();


    boolean slidingWindowsTryAcquire(){
        Long currentWindowTime = System.currentTimeMillis();

        //计算当前窗口的总请求数
        int currentWindowNum  = countCurrentWindow(currentWindowTime);

        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        counters.put(currentWindowTime, (counters.get(currentWindowTime)+1));
        return true;
    }

    private int countCurrentWindow(Long currentWindowTime) {
        //计算窗口的位置
        long startTime = currentWindowTime - SUB_CYCLE * (60/SUB_CYCLE -1);
        int count = 0;
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();

        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            if (entry.getKey()<startTime){
                iterator.remove();
            } else {
                count = count + entry.getValue();
            }
        }
        return count;
    }*/
}


class SystemClock{

    private final int period;

    private final AtomicLong now;

    private static class InstanceHolder{
        private static final SystemClock INSATNCE = new SystemClock(1);
    }

    public SystemClock(int period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();
    }

    private static SystemClock insatnce() {
        return InstanceHolder.INSATNCE;
    }

    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor(new ThreadFactory() {
            @Override
            public Thread newThread(Runnable r) {

                Thread thread = new Thread(r, "System Clock");
                thread.setDaemon(true);
                return thread;
            }
        });

        scheduledExecutorService.scheduleAtFixedRate(()->now.set(System.currentTimeMillis()),period, period, TimeUnit.MILLISECONDS);
    }

    private long currentTimeMillis() {
        return now.get();
    }

    public static long now() {
        return insatnce().currentTimeMillis();
    }
}
